// https://leetcode.cn/problems/set-intersection-size-at-least-two/
// Created by ade on 2022/7/22.
// 一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。
//
// 给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
//
// 输出这个最小集合S的大小。
/*
 *
输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况，故我们输出3。
示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出: 5
解释:
最小的集合S = {1, 2, 3, 4, 5}.

 * */

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


class Solution {
public:
    int intersectionSizeTwo(vector <vector<int>> &intervals) {
        int len = intervals.size();
        if (len == 1) {
            return 2;
        }
        sort(intervals.begin(), intervals.end(), [&](vector<int> &a, vector<int> &b) {
            return a[1] < b[1];
        });
        // 常规去最右侧的两个数
        vector<int> res = {intervals[0][intervals[0].size() - 1] - 1, intervals[0][intervals[0].size() - 1]};
        for (int i = 1; i < len; i++) {
            auto tmp = intervals[i];
            int iLen = tmp.size();
            if(res.back() < tmp[0]){
                // 常规去最右侧的两个数
                res.push_back(tmp[iLen - 1] - 1);
                res.push_back(tmp[iLen - 1]);
            } else if(res.back() == tmp[0]){
                // 常规去最右侧的一个数
                res.push_back(tmp[iLen - 1]);
            }else if(res[res.size() - 2] < tmp[0]){
                // 特殊情况处理：加入倒数第2个数小于tmp[0],代表当前组合只会有一个数满足要求，及res[res.size()-1]，所以需要添加最右侧的数
                res.push_back(tmp[iLen - 1]);
            }
        }
        return res.size();
    }
};

int main() {
    Solution so;
    vector <vector<int>> intervals = {{33,44},{42,43},{13,37},{24,33},{24,33},{25,48},{10,47},{18,24},{29,37},{7,34}};
    int a = so.intersectionSizeTwo(intervals);
    cout << a << endl;
    return 0;
}

